Maratones competidas/Maratón Nacional 2011/workspace/e/ebfs.cpp

   1 // Equipo Poncho, Carriel y Ruana
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 template <class T> string toStr(const T &x)
  23 { stringstream s; s << x; return s.str(); }
  24 template <class T> int toInt(const T &x)
  25 { stringstream s; s << x; int r; s >> r; return r; }
  26
  27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  29 #define D(x) cout << #x " = " << (x) << endl;
  30
  31 const double EPS = 1e-9;
  32
  33 int cmp(double x, double y = 0, double tol = EPS) {
  34     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  35 }
  36
  37 #define INPUT_FILE "edgetown"
  38
  39 const int MAXN = 105;
  40 const int oo = 1<<28;
  41
  42 int g1[MAXN][MAXN];
  43 int g2[MAXN][MAXN];
  44 int n;
  45
  46 void floyd(){
  47     For(k, 0, n) {
  48         For(i, 0, n) {
  49             For(j, 0, n) {
  50                 g1[i][j] = min(g1[i][j], g1[i][k] + g1[k][j]);
  51                 g2[i][j] = min(g2[i][j], g2[i][k] + g2[k][j]);
  52             }
  53         }
  54     }
  55 }
  56
  57 vector<int> gg1[MAXN], gg2[MAXN];
  58
  59 int dist[MAXN];
  60 void bfs(int start, vector<int> g[MAXN]) {
  61     For(i, 0, n) dist[i] = oo;
  62     queue<int> q;
  63     dist[start] = 0;
  64     q.push(start);
  65     while (q.size()) {
  66         int u = q.front();
  67         q.pop();
  68
  69         for (int k = 0; k < g[u].size(); ++k) {
  70             int v = g[u][k];
  71
  72             if (dist[v] < oo) continue;
  73             dist[v] = dist[u] + 1;
  74             q.push(v);
  75         }
  76     }
  77 }
  78
  79 bool equal(long long a, long long b) {
  80     For(i, 0, n) {
  81         For(j, 0, n) {
  82             if (g2[i][j] >= oo) return false;
  83             long long now = g2[i][j];
  84             long long cota = g1[i][j] * a + b;
  85             if (now > cota) {
  86                 //printf("From %d to %d: now = %d, cota = %d, old = %d\n", i, j, (int)now, (int)cota, g1[i][j]);
  87                 return false;
  88             }
  89         }
  90     }
  91     return true;
  92 }
  93
  94 int main(){
  95     freopen(INPUT_FILE ".in", "r", stdin);
  96     while (cin >> n) {
  97         if (n == 0) break;
  98         string s; getline(cin, s);
  99
 100         For (i, 0, n) For(j, 0, n) g1[i][j] = g2[i][j] = oo;
 101         For (i, 0, n) gg1[i].clear(), gg2[i].clear();
 102
 103         for (int i = 0; i < n; ++i) {
 104             getline(cin, s);
 105             stringstream sin(s);
 106             int first; sin >> first; first--;
 107             int other;
 108             while (sin >> other) {
 109                 other--;
 110                 g1[first][other] = 1;
 111                 gg1[first].push_back(other);
 112             }
 113         }
 114
 115         for (int i = 0; i < n; ++i) {
 116             getline(cin, s);
 117             stringstream sin(s);
 118             int first; sin >> first; first--;
 119             int other;
 120             while (sin >> other) {
 121                 other--;
 122                 g2[first][other] = 1;
 123                 gg2[first].push_back(other);
 124             }
 125         }
 126         For(i, 0, n) g1[i][i] = g2[i][i] = 0;
 127
 128         int a, b;
 129         cin >> a >> b;
 130         if (a == 0 and b == 0 and n > 1) {
 131             puts("No");
 132             continue;
 133         }
 134
 135         //puts("G1"); For(i, 0, n){  For(j, 0, n) { printf("%10d", g1[i][j]); } puts(""); } puts("");
 136         //puts("G2"); For(i, 0, n){  For(j, 0, n) { printf("%10d", g2[i][j]); } puts(""); } puts("");
 137
 138         //floyd();
 139
 140         For(i, 0, n) {
 141             bfs(i, gg1);
 142             For(j, 0, n) {
 143                 g1[i][j] = dist[j];
 144             }
 145             bfs(i, gg2);
 146             For(j, 0, n) {
 147                 g2[i][j] = dist[j];
 148             }
 149         }
 150
 151         if (equal(a, b)) {
 152             puts("Yes");
 153         } else {
 154             puts("No");
 155         }
 156     }
 157     return 0;
 158
 159 }